Not Applicable.
Not Applicable.
This invention relates to generally to a method and apparatus for transmitting of data on a communications network. More specifically, this invention relates to timely forwarding and delivery of data packet across a switch with known predefined delay, jitter and loss. Consequently, the end-to-end performance parameters, such as, loss, delay and jitter, have predefined values, which can be with either deterministic or probabilistic guarantees.
Circuit-switched networks, which are still the main carrier of streams of real-time traffic, are designed for telephony service and cannot be easily enhanced to support multiple services or carry multimedia traffic. Its synchronous byte switching enables circuit-switching networks to transport data streams at constant rates with little delay or jitter. However, since circuit-switching networks allocate resources exclusively for individual connections, they suffer from low utilization under bursty traffic. Moreover, it is difficult to dynamically allocate circuits of widely different capacities, which makes it a challenge to support multimedia traffic. Finally, the synchronous byte switching of Synchronous Optical NETwork (SONET) or Synchronous Digital Hierarchy (SDH), requires increasingly more precise clock synchronization as the lines speed increases [John C. Bellamy, xe2x80x9cDigital Network Synchronizationxe2x80x9d, IEEE Communications Magazine, April 1995, pp. 70-83].
Packet switching networks like IP (Internet Protocol)-based Internet and Intranets [see, for example, A.Tannebaum, Computer Networks (3rd Ed.) Prentice Hall, 1996] and ATM (Asynchronous Transfer Mode) [see, for example, Handel et al., ATM Networks: Concepts, Protocols, and Applications, (2nd Ed.) Addison-Wesley, 1994] handle bursty data more efficiently than circuit switching, due to their statistical multiplexing of the packet streams. However, current packet switches and routers operate asynchronously and provide xe2x80x9cbest effortxe2x80x9d service only, in which end-to-end delay and jitter are neither guaranteed nor bounded. Furthermore, statistical variations of traffic intensity often lead to congestion that results in excessive delays and loss of packets, thereby significantly reducing the fidelity of real-time streams at their points of reception.
Efforts to define advanced services for both IP and ATM networks have been conducted in two levels: (1) definition of service, and (2) specification of methods for providing different services to different packet streams. The former defines interfaces, data formats, and performance objectives. The latter specifies procedures for processing packets by hosts and switches/routers. The types of services that defined for ATM include constant bit rate (CBR), variable bit rate (VBR) and available bit rate (ABR).
The methods for providing different services under packet switching fall under the general title of Quality of Service (QoS). Prior art in QoS can be divided into two parts: (1) traffic shaping with local timing without deadline scheduling, for example [Demers et al., xe2x80x9cAnalysis and Simulation Of A Fair Queuing Algorithmxe2x80x9d, ACM Computer Communication Review (SIGCOMM""89), pp. 3-12, 1989; S. J, Golestani, xe2x80x9cCongestion Free Communication In High-Speed Packet Networksxe2x80x9d, IEEE Transcripts on Communications, COM-39(12): 1802-1812, December 1991; Parekh et. al., xe2x80x9cA Generalized Processor Sharing Approach To Flow Controlxe2x80x94-The Multiple Node Casexe2x80x9d, ACM Transactions on Networking, 2(2): 137-150, 1994], and (2) traffic shaping with deadline scheduling, for example [Ferrari et. al., xe2x80x9cA Scheme For Real-Time Channel Establishment In Wide Area Networksxe2x80x9d, IEEE Journal on Selected Areas in Communication, SAC-8(4): 368-379, April 1990]. Both of these approaches rely on manipulation of local queues by each router with little or no coordination with other routers. These approaches have inherent limitations when used to transport real-time streams. When traffic shaping without deadline scheduling is configured to operate at high utilization with no loss, the delay and jitter are inversely proportional to the connection bandwidth, which means that low rate connections may experience large delay and jitter inside the network. In traffic shaping with deadline scheduling the delay and jitter are controlled at the expense of possible congestion and loss.
The real-time transport protocol (RTP) [H. Schultzrinne et. al, xe2x80x9cRTP: A Transport Protocol for Real-Time Applicationsxe2x80x9d, IETF Request for Comment RFC1889, January 1996] is a method for encapsulating time-sensitive data packets and attaching to the data time related information like time stamps and packet sequence number. RTP is currently the accepted method for transporting real time streams over IP internetworks and packet audio/video telephony based on ITU-T H.323.
One approach to an optical network that uses synchronization was introduced in the synchronous optical hypergraph [Y. Ofek, xe2x80x9cThe Topology, Algorithms And Analysis Of A Synchronous Optical Hypergraph Architecturexe2x80x9d, Ph.D. Dissertation, Electrical Engineering Department, University of Illinois at Urbana, Report No. UIUCDCS-R-87 1343, May 1987], which also relates to how to integrate packet telephony using synchronization [Y. Ofek, xe2x80x9cIntegration Of Voice Communication On A Synchronous Optical Hypergraphxe2x80x9d, IEEE INFOCOM""88, 1988]. In the synchronous optical hypergraph, the forwarding is performed over hyper-edges, which are passive optical stars. In [Li et al., xe2x80x9cPseudo-Isochronous Cell Switching In ATM Networksxe2x80x9d, IEEE INFOCOM""94, pp. 428-437, 1994; Li et al., xe2x80x9cTime-Driven Priority: Flow Control For Real-Time Heterogeneous Internetworkingxe2x80x9d, IEEE INFOCOM""96, 1996] the synchronous optical hypergraph idea was applied to networks with an arbitrary topology and with point-to point links. The two papers [Li et al., xe2x80x9cPseudo-Isochronous Cell Switching In ATM Networksxe2x80x9d, IEEE INFOCOM""94, pages 428-437, 1994; Li et al., xe2x80x9cTime-Driven Priority: Flow Control For Real-Time Heterogeneous Internetworkingxe2x80x9d, IEEE INFOCOM""96, 1996] provide an abstract (high level) description of what is called xe2x80x9cRISC-like forwardingxe2x80x9d, in which a packet is forwarded, with little if any details, one hop every time frame in a manner similar to the execution of instructions in a Reduced Instruction Set Computer (RISC) machine.
Switching architectures for data packet have been extensively studied and developed in the past three decades, see for example [A. G. Fraser, xe2x80x9cEarly Experiment with Asynchronous Time Division Networksxe2x80x9d, IEEE Networks, pp. 12-26, January 1993. Several surveys of packet switching architectures can be found in: [E. W. Zegura, xe2x80x9cArchitecture for ATM Switching Systemsxe2x80x9d, IEEE Communications Magazine, February 1993, pages 28-37; A. Pattavina, xe2x80x9cNon-blocking Architecture for ATM Switchingxe2x80x9d, IEEE Communications Magazine, February 1993, pages 37-48; A. R. Jacob, xe2x80x9cA Survey of Fast Packet Switchesxe2x80x9d, Computer Communications Review, January 1990, pages 54-64].
In accordance with the present invention, the switch scheduling method disclosed is tailored to operate responsive to global common such that the switching delay from input to out put is deterministic and is known in advance. Consequently, such a switch can be employed in the construction of a synchronous virtual pipe (or simply a virtual pipe). Such virtual pipes can carry real-time traffic over packet switching networks while guaranteeing end-to-end performance. The switching and data packet forwarding method combines the advantages of both circuit and packet switching. It provides for allocation for the exclusive use of predefined connections and for those connections it guarantees loss free transport with low delay and jitter. When predefined connections do not use their allocated resources, other non-reserved data packets can use them without affecting the performance of the predefined connections.
Under the aforementioned prior art methods for providing packet switching services, switches and routers operate asynchronously. The present invention provides real-time services by synchronous methods that utilize a time reference that is common to the switches and end stations comprising a wide area network. The common time reference can be realized by using UTC (Coordinated Universal Time), which is globally available via, for example, GPS (Global Positioning Systemxe2x80x94see, for example: [Peter H. Dana, xe2x80x9cGlobal Positioning System (GPS) Time Dissemination for Real-Time Applicationsxe2x80x9d, Real-Time Systems, 12, pp. 9-40, 1997]. By international agreement, UTC is the same all over the world. UTC is the scientific name for what is commonly called GMT (Greenwich Mean Time), the time at the 0 (root) line of longitude at Greenwich, England. In 1967, an international agreement established the length of a second as the duration of 9,192,631,770 oscillations of the cesium atom. The adoption of the atomic second led to the coordination of clocks around the world and the establishment of UTC in 1972. The Time and Frequency Division of the National Institute of Standards and Technologies (NIST) (see http://www.boulder.nist.gov/timefreq) is responsible for coorinating UTC with the International Bureau of Weights and Measures (BIPM) in Paris.
UTC timing is readily available to individual PCs through GPS cards. For example, TrueTime, Inc. (Santa Rosa, Calif.) offers a product under the tradename PCI-SG which provides precise time, with zero latency, to computers that have PCI extension slots. Another way by which UTC can be provided over a network is by using the Network Time Protocol (NTP) [D. Mills, xe2x80x9cNetwork Time Protocolxe2x80x9d (version 3) IETF RFC 1305]. However, the clock accuracy of NTP is not adequate for inter-switch coordination, on which this invention is based.
In accordance with the present invention, the synchronization requirements are independent of the physical link transmission speed, while in circuit switching the synchronization becomes more and more difficult as the link speed increases.
In accordance with the present invention, timing information is not used for routing, and therefore, in the Internet, for example, the routing is done using IP addresses or an IP tag/label.